#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* nonsensical hyphens to make greedy wrapping method look bad */
const char *string = "In olden times when wishing still helped one, there lived a king "
    "whose daughters were all beautiful, but the youngest was so beautiful "
    "that the sun itself, which has seen so much, was astonished whenever "
    "it shone in her face. Close by the king's castle lay a great dark "
    "forest, and under an old lime tree in the forest was a well, and when "
    "the day was very warm, the king's child went out into the forest and "
    "sat down by the side of the cool fountain, and when she was bored she "
    "took a golden ball, and threw it up on high and caught it, and this "
    "ball was her favorite plaything.";

/*  Each but the last of wrapped lines comes with some penalty as the square
    of the diff between line length and desired line length.  If the line
    is longer than desired length, the penalty is multiplied by 100.  This
    pretty much prohibits the wrapping routine from going over right margin.
    If is ok to exceed the margin just a little, something like 20 or 40 will
    do.

    Knuth uses a per-paragraph penalty for line-breaking in TeX, which is--
    unlike what I have here--probably bug-free.
*/

#define PENALTY_LONG    100
#define PENALTY_SHORT   1

typedef struct word_t {
    const char *s;
    int len;
} *word;

word make_word_list(const char *s, int *n)
{
    int max_n = 0;
    word words = 0;

    *n = 0;
    while (1) {
        while (*s && isspace(*s)) s++;
        if (!*s) break;

        if (*n >= max_n) {
            if (!(max_n *= 2)) max_n = 2;
            words = realloc(words, max_n * sizeof(*words));
        }
        words[*n].s = s;
        while (*s && !isspace(*s)) s++;
        words[*n].len = s - words[*n].s;
        (*n) ++;
    }

    return words;
}

int greedy_wrap(word words, int count, int cols, int *breaks)
{
    int score = 0, line, i, j, d;

    i = j = line = 0;
    while (1) {
        if (i == count) {
            breaks[j++] = i;
            break;
        }

        if (!line) {
            line = words[i++].len;
            continue;
        }

        if (line + words[i].len < cols) {
            line += words[i++].len + 1;
            continue;
        }

        breaks[j++] = i;
        if (i < count) {
            d = cols - line;
            if (d > 0)  score += PENALTY_SHORT * d * d;
            else if (d < 0) score += PENALTY_LONG * d * d;
        }

        line = 0;
    }
    breaks[j++] = 0;

    return score;
}

void show_wrap(word list, int count, int *breaks)
{
    int i, j;
    for (i = j = 0; i < count && breaks[i]; i++) {
        while (j < breaks[i]) {
            printf("%.*s", list[j].len, list[j].s);
            if (j < breaks[i] - 1)
                putchar(' ');
            j++;
        }
        if (breaks[i]) putchar('\n');
    }
}

int main(void)
{
    int len, score, cols;
    word list = make_word_list(string, &len);
    int *breaks = malloc(sizeof(int) * (len + 1));

    cols = 80;
    score = greedy_wrap(list, len, cols, breaks);
    //printf("\n== greedy wrap at %d (score %d) ==\n\n", cols, score);
    show_wrap(list, len, breaks);

    //score = balanced_wrap(list, len, cols, breaks);
    //printf("\n== balanced wrap at %d (score %d) ==\n\n", cols, score);
    //show_wrap(list, len, breaks);


    //cols = 32;
    //score = greedy_wrap(list, len, cols, breaks);
    //printf("\n== greedy wrap at %d (score %d) ==\n\n", cols, score);
    //show_wrap(list, len, breaks);

    //score = balanced_wrap(list, len, cols, breaks);
    //printf("\n== balanced wrap at %d (score %d) ==\n\n", cols, score);
    //show_wrap(list, len, breaks);

    return 0;
}
